package Leetcode.网格图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Author: kirito
 * @Date: 2024/4/26 12:41
 * @Description:
 * 16.19. 水域大小
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。
 * 若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。
 * 池塘的大小是指相连接的水域的个数。
 * 编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
 *
 * 示例：
 *
 * 输入：
 * [
 *   [0,2,1,0],
 *   [0,1,0,1],
 *   [1,1,0,1],
 *   [0,1,0,1]
 * ]
 * 输出： [1,2,4]
 * 提示：
 *
 * 0 < len(land) <= 1000
 * 0 < len(land[i]) <= 1000
 */

public class pondSizes {
    public static void main(String[] args) {
        int[][] arr = {
                {0,2,1,0},
                {0,1,0,1},
                {1,1,0,1},
                {0,1,0,1}
        };
        System.out.println(Arrays.toString(
                new pondSizes().pondSizes(arr)
        ));
    }

    public int[] pondSizes(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 0) {
                    int res = area(grid, r, c);
                    list.add(res);
                }
            }
        }
        int size = list.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; i++) {
            ans[i] = list.get(i);
        }
        Arrays.sort(ans);
        return ans;

    }



    int area(int[][] grid, int r, int c) {
        if (0 > r
                || r >= grid.length
                || 0 > c
                || c >= grid[0].length) {
            return 0;
        }
        if (grid[r][c] != 0) {
            return 0;
        }
        /*
        保证方格不进行重复遍历。标记遍历过的方格并不需要使用额外的空间，
        只需要改变方格中存储的值就可以。
        在这道题中，值为 0 表示非岛屿（不可遍历），
        值为 1 表示岛屿（可遍历），
        我们用 2 表示已遍历过的岛屿。
         */
        grid[r][c] = 2;
        return 1
                + area(grid, r - 1, c)
                + area(grid, r + 1, c)
                + area(grid, r, c - 1)
                + area(grid, r, c + 1)
                + area(grid, r - 1, c - 1)
                + area(grid, r + 1, c + 1)
                + area(grid, r + 1, c - 1)
                + area(grid, r - 1, c + 1);
    }
}
